package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func rightSideView(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	queue := []*TreeNode{
		root,
	}
	depths := make(map[*TreeNode]int)
	depths[root] = 0
	var result []int
	for len(queue) > 0 {
		head := queue[0]
		copy(queue, queue[1:])
		queue = queue[:len(queue)-1]
		depth := depths[head]
		if len(result) <= depth { // first of depth
			result = append(result, head.Val)
		}
		if head.Right != nil {
			queue = append(queue, head.Right)
			depths[head.Right] = depth + 1
		}
		if head.Left != nil {
			queue = append(queue, head.Left)
			depths[head.Left] = depth + 1
		}
	}
	return result
}

func main() {

}
